Scheduling multithreaded computations on multiprocessor machines has been the source of much research. To execute multithreaded computations, the operating system runs a collection of kernel-level processes, one per processor, and each of these processes controls the execution of multiple computational threads created dynamically by the executed program. The scheduling problem is that of dynamically deciding which thread is to be run by which process at a given time, so as to maximize the utilization of the available computational resources (processors). Thread is short for thread of execution. A thread is a sequence of instructions which may execute in parallel with other sequences of instructions.
Most of today's multi-processor machines run programs in a multi-programmed mode, where the number of processors used by a computation grows and shrinks over time. In such a mode, each program has its own set of processes, and the operating system chooses in each step which subset of these processes to run, according to such factors as the nature, size, and number of processors available for that program at the time, the amount of work load waiting to be performed, the nature, size, and number of memory modules, and so on. Therefore the scheduling algorithm is dynamic (as opposed to static): at each step it schedules threads onto processes, without knowing which of the processes or work tasks are going to be run.
When a program is executed on a multiprocessor machine, the threads of computation are dynamically generated by the different processes, implying that the scheduling algorithm generated in a scheduler has processes load balance the computational work in a distributed fashion. The challenge in designing such distributed work scheduling algorithms is that performing a re-balancing, even between a pair of processes, requires the use of costly synchronization operations.